1. Field of the Invention
The present invention generally relates to a system and method of using wireless communication devices as beacons to allow a target wireless communication device to determine its location, and, more particularly, the present invention relates to using a collection of beacon devices that communicate using a wireless channel and a common protocol with a target device using this channel and protocol.
2. Description of the Related Art
In mobile computing, the location of the user becomes a fundamental parameter in many applications and services. The ability to automatically and accurately obtain the location of a user or other communicating devices in a wireless networked environment is an enabling step in the development of many new-applications and services such as tour-guide systems, people/animal/object tracking, inventory management, healthcare, area monitoring and digital shopping assistants (Jonathan Agre, Adedeji Akinyemi, Lusheng Ji, Ryusuke Masuoka, and Pankaj Thakkar, “A Layered Architecture for Location-based Services in Wireless Ad Hoc Networks,” IEEE Aerospace Conference, March, 2002, Big Sky, Mont., USA.).
The E911 requirements proposed by the U.S. Federal Communications Commission in which cellular telephone carriers are required to implement a system for location determination of a wireless telephone that is used to dial an emergency 911 call, to a specified accuracy, is one prominent example of a location-aware service (Reed, J. H., Krizman, K. J., Woerner, B. D., and Rappaport, T. S., “An overview of the challenges and progress in meeting the E-911 requirement for location service,” IEEE Communications Magazine, Vol. 36, No. 4, pp 30-37, April, 1998).
There are many methods of automatically determining the location of an object. These methods range from Global Positioning System (GPS)-solutions, acoustic, infrared or radio-frequency sensors, to inertial navigation systems. Each method has advantages and disadvantages in various environments (e.g., indoors, outdoors), yielding differences in metrics such as accuracy, repeatability, computational complexity, power consumption, ease of use, cost and infrastructure requirements. In addition, different methods have advantages or disadvantages in supporting requirements for client privacy and control of location information. In many applications of interest, ease of use and deployment are more important than high degrees of accuracy. Since there is no one technology that can address all environments and requirements, it is likely that many different determination methods will be needed to support various location aware applications.
Some location-determination schemes can be fully implemented in an isolated client device, such as a GPS navigation device, although there is a large cost in infrastructure and deployment of the satellites. Other systems determine the client location in system servers, such as those employed at base stations in cellular telephone systems. Location information is often considered sensitive and private and in general, a client-based scheme is deemed to offer better privacy control for the user.
A particular location determination method may or may not depend on a two-way communications infrastructure as an integral part. In many systems, a two-way communication network is already incorporated in the devices for interaction with the remote location-aware applications. This communication capability can then also be used for location determination (as in base station solutions to the E911 problem). In these cases, there can be a cost and system complexity advantage, if there is a radio transmitter and receiver on the device, and these can also be used for location measurements.
A beacon is a device at a known location that emits a signal that is used by a client to determine its location. Some examples of beacons include lighthouses, LORAN transmitters and GPS satellites. Various techniques are used in conjunction with the beacon signal to actually obtain a “fix” or precise knowledge of the client position. These techniques can be as simple as proximity to the beacon (as with a lighthouse and a map) or as complex as estimating range to multiple beacons and then using triangulation or multilateration.
There exist many different approaches to location determination based on different technologies such as radio frequency (RF) communication, infra-red (IR), visual, acoustic, electromagnetic field change, gyroscopic (inertial navigation), laser ranging and radar techniques. Each technology has inherent strengths and weaknesses depending on many factors: accuracy, environment (e.g., temperature, pressure, wind, ambient light), power, infrastructure requirements, susceptibility to noise, etc.
A target (or client) is an item whose location is to be found. In different schemes, the target can be completely passive, or either a source (transmitter) or a sink (receiver) or both. The basic techniques used by these technologies can be broadly classified in the following four categories:
1. Geometric: This typically involves taking multiple measurements between different transmitter-receiver sets and the target. When the measurements are used to find the distance or range between a transmitter and the receiver, the method is called triangulation via lateration (or multi-lateration) and when those are used to find angles, the method is called triangulation via angulation.
2. Proximity: Measure the nearness of a target to a known set of points. The nearness is a relative term as opposed to a range estimate. For example, if a target is communicating with a base station, it must be somewhere within the geographic coverage area of that station.
3. Pattern recognition: The system is set up by taking measurements in the area of interest over a large number of grid points using transmitter/receiver pairs and storing them in a map file. A measurement is made of the target and then statistical methods are used to determine the target's most likely position.
4. Scene analysis: Examines a scene in a sensor's field of view from a particular vantage point. This is typically done via cameras that use image processing to recognize changes in objects within their area of coverage and estimate location.
Different methods use these technologies and categories individually or in combination to determine location. For example, GPS uses time-of-arrival (TOA) of radio frequency signals from several satellite transmitters at a target's receiver to estimate range to the satellites and then uses multi-lateration to determine position to within 20 m. Differential GPS uses the difference between the satellite and a local reference signal to improve that accuracy to within 1 m. An example of a hybrid system uses a radio channel for synchronization and a relatively slower ultrasonic signal TOA to compute range and then uses multi-lateration. The RADAR system uses RF pattern analysis based on the minimum distance estimates obtained from a combination of signal strength, TOA and angle-of-arrival (AOA) (Bahl, P. and Padmanabhan, V., “Radar: An in-building RF-based user location and tracking system,” IEEE Infocom, Tel Aviv, Isreal, pp. 775-784, March, 2000). A survey of the state-of-the-art in location determination methods can be found in (Hightower, J. and Borriello, G., “Location systems for ubiquitous computing,” IEEE Computer, Vol. 34, No. 8, pp. 57-65, August, 2001).
RF-based schemes include a low cost of transmitters and receivers and are unaffected by light, temperature, wind and non-metallic barriers. Also, if they can be combined with the necessary RF communication components and infrastructure, then there are potential savings in both size and component cost.
There has been recent work on using cellular telephony RF-based schemes as part of the E-911 requirements (Reed, J. H., Krizman, K. J., Woerner, B. D., and Rappaport, T S., “An overview of the challenges and progress in meeting the E-911 requirement for location service,” IEEE Communications Magazine, Vol. 36, No. 4, pp 30-37, April, 1998). These are either handset-based—primarily using GPS and base-station-based schemes. These include methods based on proximity, geometric schemes using received signal strength (RSS), time of arrival (TOA) and angle of arrival (AOA), and pattern matching. Proximity and pattern matching are often combined. Time of arrival and signal strength are often combined to estimate range. Accuracy of the above schemes is around 150 m.
In many applications there is a need for indoor location methods and the accuracy required indoors is generally greater than outdoors. GPS is not effective indoors, although new technologies are being introduced that are sensitive enough to operate in many indoor applications. Two of the main difficulties in indoor location methods are non-line of sight (walls) measurements and multipath due to reflections. A survey describing the indoor channel and its signal propagation characteristics, as well as candidate channel models can be found in (Pahlavan, K., Li, X. and Makela, J. P., “Indoor Geolocation Science and Technology,” IEEE Communications Magazine, pp. 112-118, February, 2002). Some additional indoor schemes include Pseudo-lite GPS, augmented GPS, CDMA-based schemes, Ultra-wideband and WLAN-based mechanisms.
One of the first indoor location systems (Wont, R. et al, “The Active Badge Location System,” ACM Transactions on Information Systems, January 1992, pp. 91-102) relied on diffuse infrared technology. Following this, several generations of indoor location systems have been developed based on a combination of ultrasound and RF. The slower propagation rate of the ultrasonic signal is easier to measure than RF. In one system, a preinstalled ceiling matrix of receivers and an RF base station are used to locate a target transmitter. The RF base station polls the transmitter (user) periodically, and after being polled, sends an ultrasonic pulse to identify itself. The receiver matrix, which not only receives the ultrasonic pulse but also receives the RF poll signal from the base-station, uses this information to find out the distance to the transmitter. In another system (Priyantha, N., Chakraborty, A. and Balakrishnan, “The Cricket Location Support System,” Proc. 6-th Annual International Conference on Mobile Computing and Networking (Mobicom 00), ACM Press, New York, N.Y., 2000, pp. 32-43), the ceiling matrix is replaced with inexpensive beacon transmitters. The transmitter (beacon) simultaneously transmits an RF and an ultra-sonic pulse. The target receiver (listener) receives both types of signal from the beacons and uses the RF for synchronization and the ultra-sonic TOA to compute the distance, find the closest beacon and identifies its location with that beacon. In yet another system that operates in the 900 MHz ISM band, signal strength is measured between nearby tags to estimate range and then determine location via lateration, in an ad hoc situation with minimal infrastructure (Hightower, J. and Want, R., “SpotON: Indoor 3-D Location Sensing from RF Signal Strength, Technical Report 2000-02-02, University of Washington, 2000).
Location Determination in WLANs is now discussed.
The rapid adoption of high speed wireless local area networks (WLANs) in the unlicensed ISM-band, such as 802.11b (a direct sequence spread spectrum scheme) and Bluetooth (a frequency hopped scheme) had led to several investigations of WLAN-based positioning schemes for mobile computing applications. These schemes typically use signal strength, TOA and/or AOA and can be classified as proximity, multilateration, triangulation and pattern matching. Several algorithms have been developed that use trending or auxiliary knowledge to increase the accuracy of the underlying technology.
There are many localization technologies that use the readily available, measured signal strengths from WLAN communications to estimate range through signal attenuation models or to perform pattern matching with a radio signal strength map of the area. Most of them use the measurements from multiple WLAN Access Points (WLAN AP's or just AP's) that are in fixed, known locations chosen for communication purposes. The measurement of signal strength can be made either on the WLAN client side or at the WLAN AP's to determine the location of a WLAN adapter (client).
These methods suffer in indoor environments where many obstacles such as walls and furniture contribute to unpredictable radio channel characteristics and multipath interference. Specific knowledge of the building structure can often be used to improve the geometric methods. Another common method is to build a radio map of the area, match the current intensity readings to those in the radio map, and then determine the location based on closest match. This usually gives better results than triangulation but it requires the user to build the radio map, a process which can take many hours. Also, if the environment changes, such as new additions of WLAN AP's, this necessitates a remapping effort.
In the indoor 802.11b environment, the pattern matching schemes seem to yield better accuracy than competing methods, primarily as they do not depend on structural knowledge of the building or on detailed modeling of the multipath environment. Typically, signal strength measurements are taken from multiple access points at known points covering the area of interest. Readings from two to more access points are usually needed to get the desired accuracy and then a pattern matching algorithm is applied. Many pattern matching schemes are feasible: clustering, fuzzy logic, Bayesian, Markov, etc. Some examples of pattern matching WLAN based schemes are: Radar, Ekahau and a spinoff from work at Carnegie-Mellon University (Smailagic, A. et al., “Location Sensing and Privacy in a Context Aware Computing Environment,” Carnegie-Mellon University, Pittsburgh, Pa., September, 2001). A problem with pattern matching is the time consuming process of building the radio maps. If any of the access points are moved or there is rearrangement of furniture, than the area must be remapped. In addition, if there is a significant change in the environment such as many people or bulky items, then the accuracy may decrease. There is also a problem with the accuracy and stability of the measurement process on commercially available 802.11b chip sets.
Other known technologies that use the proximity techniques are now discussed. Related art system 1 uses RF and ultrasonic pulses to estimate the distance between transmitter and receiver, and hence special hardware is needed on the client side. Related art system 2 also falls into this category. Here special hardware is used to identify the device. Beacons are transmitted by client devices and received at known fixed locations. The nearest receiver then notifies the client of its location. Related art system 3 (Smailagic, A. and Siewiorek, D., “User Centered Interdisciplinary Design of Wearable Computers,” ACM Mobile Computing and Communications Review, Vol. 3, No. 3, 1999, pp. 43-52) does not require any hardware on the mobile user side and the location of the mobile client is determined by the closest access point the client is currently associated with. The data access point is used to infer location, and hence the accuracy is limited to placement of the access point. Related art system 4 puts pressure sensors under the floor and then using user physical weight, one can track and identify the user. Again, the installment cost is high, since one needs to construct the floor with sensors beneath.
Types of beacon technologies are: 802.11b signal strength methods, IrDA Beacon methods, and Bluetooth signal strength methods.
An IrDA beacon includes both IrDA and Bluetooth communications and has several important features: 1) the device transmits programmable ID codes or local data using the IrDA standard communication channel and protocol, 2) angle and range (up to 7 m or 10 m) of IrDA can be adjusted horizontally (3 regions) or vertically (>550) into 6 regions. Another product is available as a kit and contains four detectors and four transmitters.
Yet a further system uses beacon devices that are placed in various locations either to represent that location or to represent an object present at that location and also to provide a URL web pointer for that location or object. The beacon periodically broadcasts a message containing the URL and any device that receives the message can access the web pages pointed to by the URL. The beacons use IR technology and the IrDA protocol.
A discussion of radio-frequency (RF) Signal Strength-based methods is now presented.
Conventional methods use either triangulation or pattern matching. In pattern matching a database of signal measurements over the covered area is maintained. The contents of the database are called attributes and may contain RF characteristics such as pilot signal strength, phase offset, time delay, angle of arrival, etc which can be used to differentiate the positions through the use of a location estimation algorithm. The database may be actually measured or it may be generated using mathematical modeling.
Also in the cellular telephony domain, there are: U.S. Pat. Nos. 5,055,851; 4,891,650; 5,218,367 that use signal strength measurements. In the '851 and '650 patents, the signal strength is measured at the base stations and used to estimate distance to four neighboring base stations and then compute the location. In the '367 patent, the measurements are made by the hand set which transmits the values to a location computation unit.
In U.S. Pat. No. 5,960,341 “Positioning systems have an RF-measurements databank”, by LeBlanc in 1999, an attribute database is constructed from a collection of measurements on uplink and downlink signal strength, transmitting power and other attributes for each basestation and a contour shape for each base station is constructed using curve fitting techniques that account for non-uniformity of the environment. When real time measurements are taken between a mobile unit and surrounding base stations, this is used to determine the intersecting contour shapes and thus location.
For example, in cellular telephony, U.S. Pat. No. 6,263,208 “Geolocation estimation methods for CDMA terminals based on pilot strength” by Chang in 2001, describes a scheme in which a mobile unit at a specific location measures the signal strength from all visible pilot signals at that location and reports those values to a location computation unit. The location computation unit determines the location probability distribution using a Bayesian algorithms and an analytical model of the RF environment. This system is primarily used in an outdoor environment and relies on a) a set of measured values and b) an analytical model of the environment that includes propagation loss, shadow fading, fast fading and measurement errors.
A method for estimating the position and velocity of a mobile unit using downlink signal strength of six basestations was described in (Hellebrandt, “Estimating the position and velocity of Mobiles in Cellular Radio Networks,” IEEE Transactions on Vehicular Technology, Vol VT-26, No 1, February 1997, pp. 7-11.). The scheme uses an attribute database and estimates the location using a least squares approach at the handset.
In U.S. Pat. No. 6,052,598 “Method for predicting the location of a mobile station in a mobile communications network,” by Rudrapatna, determines the approximate position of a mobile unit using signal strength measurements. Using a series of signal strength measurements the velocity (speed and direction) can be determined. This is used for predicting handoff times. The technique smoothes the signal strength using a rolling window. The changes in signal strength over time are estimated. Differing outdoor propagation models for each base station are used.
These techniques all have problems operating in indoor areas. Some also require compilation of a large attribute database which is a tedious and time consuming process. In addition the database must be changed if any environmental characteristics are changed (e.g., seasons). There also are the problems of relating distance to signal strength or other attributes in a general fashion. This is a complex and difficult task due to the internal structure of interior spaces.
Additional problems in related art include: 1) difficulty of system deployment and operation, 2) use in indoor environments as well as outdoor areas, 3) privacy control by client (target) with regard to disbursement of location data, 4) high total cost of operation due to device and infrastructure requirements, and 5) collection and maintenance of calibration data or radio maps when environment changes.
Moreover, signal intensity-based methods exist that rely on the construction of a signal intensity map based on extensive measurements made in the environment prior to deployment. But, if the configuration of transmitters/receivers is changed, then the area needs to be re-measured.